package leetcode.Hot100;

import leetcode.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 * <p>
 * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/5 15:59
 */
public class flatten {
    public static void main(String[] args) {
        TreeNode a = new TreeNode(3);
        TreeNode b = new TreeNode(4);
        TreeNode c = new TreeNode(2, a, b);
        TreeNode d = new TreeNode(6);
        TreeNode e = new TreeNode(5, null, d);
        TreeNode f = new TreeNode(1, c, e);

        flatten(f);
        // flatten1(f);
    }

    // 传入一个节点，先将 node.left.right = node.right, 然后node.right = node.left ===》 思路错误
    // 传入一个节点，把这个节点 展开为一个单链表 左子节点的最后的右边叶子节点 放 右节点
    static void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.left);
        flatten(root.right);
        // root.left 必须存在
        if (root.left == null) return;
        TreeNode temp = root.left;
        // 找到 root.left 链表的尾节点
        while (temp.right != null) {
            temp = temp.right;
        }
        // root.left的尾节点接上 root.right
        temp.right = root.right;
        // root.left 变为 root.right
        root.right = root.left;
        // root.left 置为null
        root.left = null;
    }

    // 写出一个树的先序遍历
    static void flatten1(TreeNode root) {
        List<TreeNode> nodeList = new ArrayList<>();
        preTraverse(root, nodeList);
        for (int i = 1; i < nodeList.size(); i++) {
            TreeNode prev = nodeList.get(i - 1), curr = nodeList.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }

    static void preTraverse(TreeNode node, List<TreeNode> nodeList) {
        if (node != null) {
            nodeList.add(new TreeNode(node.val));
            preTraverse(node.left, nodeList);
            preTraverse(node.right, nodeList);
        }
    }

}
